/*
 Author: Corneliu S. (github.com/upphiminn)
 This is a javascript implementation of the Louvain
 community detection algorithm (http://arxiv.org/abs/0803.0476)
 Based on https://bitbucket.org/taynaud/python-louvain/overview
 */
jLouvain = function () {
    //Constants
    var __PASS_MAX = -1;
    var __MIN = 0.0000001;

    //Local vars
    var original_graph_nodes;
    var original_graph_edges;
    var original_graph = {};
    var partition_init;

    //Helpers
    function make_set(array) {
        var set = {};
        array.forEach(function (d, i) {
            set[d] = true;
        });

        return Object.keys(set);
    }

    function obj_values(obj) {
        var vals = [];
        for (var key in obj) {
            if (obj.hasOwnProperty(key)) {
                vals.push(obj[key]);
            }
        }

        return vals;
    }

    function get_degree_for_node(graph, node) {
        var neighbours = graph._assoc_mat[node] ? Object.keys(graph._assoc_mat[node]) : [];
        var weight = 0;
        neighbours.forEach(function (neighbour, i) {
            var value = graph._assoc_mat[node][neighbour] || 1;
            if (node === neighbour) {
                value *= 2;
            }
            weight += value;
        });

        return weight;
    }

    function get_neighbours_of_node(graph, node) {
        if (typeof graph._assoc_mat[node] === 'undefined') {
            return [];
        }

        var neighbours = Object.keys(graph._assoc_mat[node]);

        return neighbours;
    }


    function get_edge_weight(graph, node1, node2) {
        return graph._assoc_mat[node1] ? graph._assoc_mat[node1][node2] : undefined;
    }

    function get_graph_size(graph) {
        var size = 0;
        graph.edges.forEach(function (edge) {
            size += edge.weight;
        });

        return size;
    }

    function add_edge_to_graph(graph, edge) {
        update_assoc_mat(graph, edge);

        var edge_index = graph.edges.map(function (d) {
            return d.source + '_' + d.target;
        }).indexOf(edge.source + '_' + edge.target);

        if (edge_index !== -1) {
            graph.edges[edge_index].weight = edge.weight;
        } else {
            graph.edges.push(edge);
        }
    }

    function make_assoc_mat(edge_list) {
        var mat = {};
        edge_list.forEach(function (edge, i) {
            mat[edge.source] = mat[edge.source] || {};
            mat[edge.source][edge.target] = edge.weight;
            mat[edge.target] = mat[edge.target] || {};
            mat[edge.target][edge.source] = edge.weight;
        });

        return mat;
    }

    function update_assoc_mat(graph, edge) {
        graph._assoc_mat[edge.source] = graph._assoc_mat[edge.source] || {};
        graph._assoc_mat[edge.source][edge.target] = edge.weight;
        graph._assoc_mat[edge.target] = graph._assoc_mat[edge.target] || {};
        graph._assoc_mat[edge.target][edge.source] = edge.weight;
    }

    function clone(obj) {
        if (obj === null || typeof(obj) !== 'object')
            return obj;

        var temp = obj.constructor();

        for (var key in obj) {
            temp[key] = clone(obj[key]);
        }

        return temp;
    }

    //Core-Algorithm Related
    function init_status(graph, status, part) {
        status['nodes_to_com'] = {};
        status['total_weight'] = 0;
        status['internals'] = {};
        status['degrees'] = {};
        status['gdegrees'] = {};
        status['loops'] = {};
        status['total_weight'] = get_graph_size(graph);

        if (typeof part === 'undefined') {
            graph.nodes.forEach(function (node, i) {
                status.nodes_to_com[node] = i;
                var deg = get_degree_for_node(graph, node);

                if (deg < 0)
                    throw 'Bad graph type, use positive weights!';

                status.degrees[i] = deg;
                status.gdegrees[node] = deg;
                status.loops[node] = get_edge_weight(graph, node, node) || 0;
                status.internals[i] = status.loops[node];
            });
        } else {
            graph.nodes.forEach(function (node, i) {
                var com = part[node];
                status.nodes_to_com[node] = com;
                var deg = get_degree_for_node(graph, node);
                status.degrees[com] = (status.degrees[com] || 0) + deg;
                status.gdegrees[node] = deg;
                var inc = 0.0;

                var neighbours = get_neighbours_of_node(graph, node);
                neighbours.forEach(function (neighbour, i) {
                    var weight = graph._assoc_mat[node][neighbour];

                    if (weight <= 0) {
                        throw "Bad graph type, use positive weights";
                    }

                    if (part[neighbour] === com) {
                        if (neighbour === node) {
                            inc += weight;
                        } else {
                            inc += weight / 2.0;
                        }
                    }
                });
                status.internals[com] = (status.internals[com] || 0) + inc;
            });
        }
    }

    function __modularity(status) {
        var links = status.total_weight;
        var result = 0.0;
        var communities = make_set(obj_values(status.nodes_to_com));

        communities.forEach(function (com, i) {
            var in_degree = status.internals[com] || 0;
            var degree = status.degrees[com] || 0;
            if (links > 0) {
                result = result + in_degree / links - Math.pow((degree / (2.0 * links)), 2);
            }
        });

        return result;
    }

    function __neighcom(node, graph, status) {
        // compute the communities in the neighb. of the node, with the graph given by
        // node_to_com
        var weights = {};
        var neighboorhood = get_neighbours_of_node(graph, node);//make iterable;

        neighboorhood.forEach(function (neighbour, i) {
            if (neighbour !== node) {
                var weight = graph._assoc_mat[node][neighbour] || 1;
                var neighbourcom = status.nodes_to_com[neighbour];
                weights[neighbourcom] = (weights[neighbourcom] || 0) + weight;
            }
        });

        return weights;
    }

    function __insert(node, com, weight, status) {
        //insert node into com and modify status
        status.nodes_to_com[node] = +com;
        status.degrees[com] = (status.degrees[com] || 0) + (status.gdegrees[node] || 0);
        status.internals[com] = (status.internals[com] || 0) + weight + (status.loops[node] || 0);
    }

    function __remove(node, com, weight, status) {
        //remove node from com and modify status
        status.degrees[com] = ((status.degrees[com] || 0) - (status.gdegrees[node] || 0));
        status.internals[com] = ((status.internals[com] || 0) - weight - (status.loops[node] || 0));
        status.nodes_to_com[node] = -1;
    }

    function __renumber(dict) {
        var count = 0;
        var ret = clone(dict); //deep copy :)
        var new_values = {};
        var dict_keys = Object.keys(dict);
        dict_keys.forEach(function (key) {
            var value = dict[key];
            var new_value = typeof new_values[value] === 'undefined' ? -1 : new_values[value];
            if (new_value === -1) {
                new_values[value] = count;
                new_value = count;
                count = count + 1;
            }
            ret[key] = new_value;
        });

        return ret;
    }

    function __one_level(graph, status) {
        //Compute one level of the Communities Dendogram.
        var modif = true;
        var nb_pass_done = 0;
        var cur_mod = __modularity(status);
        var new_mod = cur_mod;

        while (modif && nb_pass_done !== __PASS_MAX) {
            cur_mod = new_mod;
            modif = false;
            nb_pass_done += 1

            graph.nodes.forEach(function (node, i) {
                var com_node = status.nodes_to_com[node];
                var degc_totw = (status.gdegrees[node] || 0) / (status.total_weight * 2.0);
                var neigh_communities = __neighcom(node, graph, status);
                __remove(node, com_node, (neigh_communities[com_node] || 0.0), status);
                var best_com = com_node;
                var best_increase = 0;
                var neigh_communities_entries = Object.keys(neigh_communities);//make iterable;

                neigh_communities_entries.forEach(function (com, i) {
                    var incr = neigh_communities[com] - (status.degrees[com] || 0.0) * degc_totw;
                    if (incr > best_increase) {
                        best_increase = incr;
                        best_com = com;
                    }
                });

                __insert(node, best_com, neigh_communities[best_com] || 0, status);

                if (best_com !== com_node) {
                    modif = true;
                }
            });
            new_mod = __modularity(status);
            if (new_mod - cur_mod < __MIN) {
                break;
            }
        }
    }

    function induced_graph(partition, graph) {
        var ret = {nodes: [], edges: [], _assoc_mat: {}};
        var w_prec, weight;
        //add nodes from partition values
        var partition_values = obj_values(partition);
        ret.nodes = ret.nodes.concat(make_set(partition_values)); //make set
        graph.edges.forEach(function (edge, i) {
            weight = edge.weight || 1;
            var com1 = partition[edge.source];
            var com2 = partition[edge.target];
            w_prec = (get_edge_weight(ret, com1, com2) || 0);
            var new_weight = (w_prec + weight);
            add_edge_to_graph(ret, {'source': com1, 'target': com2, 'weight': new_weight});
        });

        return ret;
    }

    function partition_at_level(dendogram, level) {
        var partition = clone(dendogram[0]);
        for (var i = 1; i < level + 1; i++) {
            Object.keys(partition).forEach(function (key, j) {
                var node = key;
                var com = partition[key];
                partition[node] = dendogram[i][com];
            });
        }

        return partition;
    }


    function generate_dendogram(graph, part_init) {
        if (graph.edges.length === 0) {
            var part = {};
            graph.nodes.forEach(function (node, i) {
                part[node] = node;
            });
            return part;
        }
        var status = {};

        init_status(original_graph, status, part_init);
        var mod = __modularity(status);
        var status_list = [];
        __one_level(original_graph, status);
        var new_mod = __modularity(status);
        var partition = __renumber(status.nodes_to_com);
        status_list.push(partition);
        mod = new_mod;
        var current_graph = induced_graph(partition, original_graph);
        init_status(current_graph, status);

        while (true) {
            __one_level(current_graph, status);
            new_mod = __modularity(status);
            if (new_mod - mod < __MIN) {
                break;
            }

            partition = __renumber(status.nodes_to_com);
            status_list.push(partition);

            mod = new_mod;
            current_graph = induced_graph(partition, current_graph);
            init_status(current_graph, status);
        }

        return status_list;
    }

    var core = function () {
        var status = {};
        var dendogram = generate_dendogram(original_graph, partition_init);

        return partition_at_level(dendogram, dendogram.length - 1);
    };

    core.nodes = function (nds) {
        if (arguments.length > 0) {
            original_graph_nodes = nds;
        }

        return core;
    };

    core.edges = function (edgs) {
        if (typeof original_graph_nodes === 'undefined')
            throw 'Please provide the graph nodes first!';

        if (arguments.length > 0) {
            original_graph_edges = edgs;
            var assoc_mat = make_assoc_mat(edgs);
            original_graph = {
                'nodes': original_graph_nodes,
                'edges': original_graph_edges,
                '_assoc_mat': assoc_mat
            };
        }

        return core;

    };

    core.partition_init = function (prttn) {
        if (arguments.length > 0) {
            partition_init = prttn;
        }
        return core;
    };

    return core;
}

module.exports = jLouvain;